Conventional networked computer systems employ switching devices such as routers, switches, and hubs to transmit data traffic. Such conventional systems typically employ a variety of transmission line media each having a particular bandwidth, or transmission speed. Data traffic transmission by a user, typically a packet or set of packets, is likewise designated a particular transmission speed, depending on a variety of factors including QOS (Quality of Service), data type, hardware type, fee-based subscription of the user, and other criteria. In a conventional channelized switching device, a physical transmission line medium, or line, is typically subdivided into a plurality of logical interfaces, each of which is apportioned a bandwidth segment from the total bandwidth of the line. Accordingly, such a channelized switching device typically employs a plurality of logical interfaces, or channels, each interface having a particular transmission speed. In a conventional device, the transmission speeds of the different logical interfaces can vary by an order of magnitude or more.
Conventional switching devices employ a variety of known layer-1 technologies, such as SONET (Synchronous Optical Network), DS-1 (Digital Signal 1), so called DS-3 (Digital Signal 3), T1, OC-12 (Optical Carrier-12), and DS-0. Such a switching device may subdivide a physical layer-1 connection into a plurality of logical interfaces, or channels, each capable of supporting packetized user traffic according to a layer-2 protocol such as HDLC or PPP. In a switching device supporting both DS-0 and DS-3 lines, for example, a single DS-3 line may be subdivided, or channelized, into 672 DS-0 logical interfaces. Alternatively, the DS-3 line may be employed as a single logical and physical interface, or so-called clearchannel traffic stream.
In such conventional switching devices, a mix of clearchannel lines and logical interfaces (channels) typically coexist. The switch multiplexes the logical interfaces over the physical interfaces connected to the ports on the device. This configuration requires the device to switch data traffic among many lines at many different speeds according to the logical interfaces superimposed over the physical interfaces connected to ports. In a typical conventional switching device with a highly channelized configuration, there may be hundreds of thousands of logical interfaces, or flows, emanating from the device at various bandwidths, or transmission speeds. The switching device schedules and transmits message traffic among the logical interfaces to attempt to maintain utilization of the outgoing lines and reduce ingress and egress queuing of message traffic.
In a conventional switching device, the device transmits message traffic, or messages, at periodic transmission intervals according to a device speed, a line speed, and multiplexing logic in effect in the device. Efficient utilization requires that message traffic is ready for transmission for each such transmission interval in which an outgoing line is ready to transmit a message. If a message is not ready to transmit during a particular transmission interval, a void transmission gap, or so-called “bubble” is created in which no message traffic travels on the line, resulting in less than full utilization.
A conventional switching device typically employs a scheduler having scheduling logic to schedule and allocate the logical interfaces. In such a scheduled system, contenders (e.g., logical queues) are scheduled for a scarce resource (e.g., transmission lines) according to the scheduling logic. Conventional schedulers arrange traffic according to a prioritization scheme, such as size or QOS (Quality of Service) into sets or queues contending for outgoing transmission lines. In such a set, the worst-case delay for a particular message is the scenario in which all other messages drain from the queue first. This model is described in further detail in Parekh, (A. K. J. Parekh, “A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks;” MIT Laboratory for Information and Decision Systems, Report LIDS-TH-2089, February, 1992). The limit expressed by this scenario is referred to as the Parekh bounds.
The Parekh bounds, therefore, indicate the worst-case wait time for a logical queue. Scheduling logical queue traffic according to the Parekh bounds ensures that each message in the respective logical queue is not queued longer than a specified maximum, because the scheduler visits each queue with a frequency sufficient to maintain the desired speed for each entry in the queued set regardless of the ordering within the set.